package com.njupt.LinkTable;


public class GetIntersectionNode {

    /**
     * 暴力解法
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        ListNode p = headA;
        ListNode q = headB;
        while (p != null) {

            while (q != null) {
                if (q != p) {
                    q = q.next;
                } else {
                    return q;
                }
            }
            q = headB;
            p = p.next;


        }
        return null;
    }

    /**
     * 遍历一次链表。因为重叠的部分一定是在后头，所以我们需要将长的链表遍历到短的链表的同一个位置
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        int countA = 0, countB = 0;
        while (curA != null) {
            countA++;
            curA = curA.next;
        }
        while (curB != null) {
            countB++;
            curB = curB.next;
        }
        curA = headA;
        curB = headB;
        int gap = countA > countB ? countA - countB : countB - countA;

        if (countB > countA) {
            int temp = 0;
            temp = countA;
            countA = countB;
            countB = temp;

            ListNode cur_temp = null;
            cur_temp = curA;
            curA = curB;
            curB = cur_temp;
        }
        while (gap > 0) {
            curA = curA.next;
            gap--;
        }
        while (curA != null) {
            if (curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }


        return null;
    }

    public void printList(ListNode head) {
        ListNode p = head;
        while (p != null) {
            System.out.print(p.val + " ");
            p = p.next;
        }
    }

    public static void main(String[] args) {
        ListNode headA = new ListNode(4);
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(8);
        ListNode node3 = new ListNode(4);
        ListNode node4 = new ListNode(5);

        headA.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;


        ListNode headB = new ListNode(5);
        ListNode node5 = new ListNode(0);
        ListNode node6 = new ListNode(1);

        headB.next = node5;
        node5.next = node6;
        node6.next = node2;


        GetIntersectionNode test = new GetIntersectionNode();
        ListNode list = test.getIntersectionNode1(headA, headB);
        test.printList(list);

    }
}
